import re

class odict(dict):
    """implements an ordered dictionary by keeping track of the order of the keys

    >>> order_dict = odict( [(5, 'x'), (7,'r'), (1, 'err')] )
    >>> for key in order_dict:
    ...     print key
    ... 
    5
    7
    1
    >>> order_dict
    ordered dict {5: 'x', 7: 'r', 1: 'err'}
    """

    key_regexp = re.compile('[a-zA-Z](\d+)$')

    def __init__(self, dct = None):
        def key_val(key):
            return int(self.key_regexp.search(key).groups()[0])

        def cmp_keys(key1, key2):
            return cmp(key_val(key1), key_val(key2))
        
        if isinstance(dct, dict):
            self._keys = dct.keys()
            self._keys.sort(cmp_keys)
            new_dict = dct
        else:
            self._keys = []
            new_dict = {}
            for key, value in dct:
                self._keys.append(key)
                new_dict[key] = value    
        dict.__init__(self, new_dict)

    def __delitem__(self, key):
        self.__delitem__(self, key)
        self._keys.remove(key)

    def __setitem__(self, key, item):
        dict.__setitem__(self, key, item)
        if key not in self._keys: self._keys.append(key)

    def clear(self):
        dict.clear(self)
        self._keys = []

    def copy(self):
        dict = dict.copy(self)
        dict._keys = self._keys[:]
        return dict

    def items(self):
        return zip(self._keys, self.values())

    def keys(self):
        return self._keys

    def popitem(self):
        try:
            key = self._keys[-1]
        except IndexError:
            raise KeyError('dictionary is empty')

        val = self[key]
        del self[key]

        return (key, val)

    def setdefault(self, key, failobj = None):
        dict.setdefault(self, key, failobj)
        if key not in self._keys: self._keys.append(key)

    def update(self, dct):
        dict.update(self, dict)
        for key in dct.keys():
            if key not in self._keys: self._keys.append(key)

    def values(self):
        return map(self.get, self._keys)

    def __iter__(self):
        return self.odict_iter(self._keys)

    def __repr__(self):
        entry = lambda ky: repr(ky) + ': ' + repr(self[ky])

        rep = 'ordered dict {' + entry(self._keys[0])  

        for key in self._keys[1:]:
            rep += ', ' + entry(key)
        return rep + '}'


    class odict_iter(object):
        
        def __init__(self, keys):
            self._keys = keys
            self.index = -1
    
        def __iter__(self):
            return self    
    
        def next(self):
            if self.index+1 >= len(self._keys):
                raise StopIteration

            self.index += 1
            return self._keys[self.index]

